updated: 2022-02-25_10:58:15-05:00

  • THE SHORT VERSION: Covers Chapters 1, 2, 3 (less emphasis on Ch. 1). If you've done it on a homework or seen it in a lecture example, it's fair game on the midterm.
  • THE LONGER VERSION: IMPORTANT NOTE: This list may not be exhaustive. The exam will include ALL material that we have covered to date.
    • Recurrence relations
    • Proofs: direct proof, proof by contradiction, mathematical (weak) induction
    • Calculate the processing speedup of one machine compared to another
    • Explain the meaning of O, Ω, Θ and why they are useful and important in CS
    • For some pair of functions f(n) and g(n), determine whether f(n) is in O(g(n)), f(n) is in Ω_(g(n)),_ or f(n)=Θ(g(n))__
    • Determine Θ for code fragments
    • Write an algorithm that improves on the efficiency (in time, space, or both) of a given algorithm
    • Determine upper or lower bounds of an algorithm
    • Discuss applying asymptotic analysis to problems
    • Difference between bounds and cases